package main

func reorderList(head *ListNode) {
	var stack = make([]*ListNode, 0)

	cur := head
	for cur != nil {
		stack = append(stack, cur)
		cur = cur.Next
	}

	cur = head
	// 1 - 2 - 3 - 4 - 5
	// 1 - 5 - 2 - 3 - 4
	// 1 - 5 - 2 - 4 - 3
	latestIndex := len(stack)
	for {
		latestIndex--

		lastNode := stack[latestIndex]
		next := cur.Next
		if lastNode == next || lastNode.Next == next {
			lastNode.Next = nil
			break
		}

		cur.Next = lastNode
		lastNode.Next = next
		cur = next
	}
}
